์ด์ง ํธ๋ฆฌ๋ ํ๋์ ๋ถ๋ชจ๊ฐ ๋ ๊ฐ์ ์์๋ฐ์ ๊ฐ์ง์ง ๋ชปํ๊ณ , ํธํฅ๋๋ค๋ฉด ํ์ ํจ์จ์ด ์ ํ ํ์๊ธ์ผ๋ก ๋จ์ด์ง๋ค. ํ์ง๋ง ์ด์ง ํธ๋ฆฌ ๊ตฌ์กฐ์ ๊ฐ๊ฒฐํจ๊ณผ ๊ท ํ๋ง ๋ง๋ค๋ฉด ํ์, ์ฝ์ , ์ญ์ ๋ชจ๋ ์ ์ฑ๋ฅ์ ๋ณด์ด๋ ์ฅ์ ์ด ์๋ค.
๐งท B Tree
๋ฐ์ดํฐ๋ฒ ์ด์ค, ํ์ผ ์์คํ ์์ ๋๋ฆฌ ์ฌ์ฉ๋๋ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ์ ์ผ์ข ์ด๋ค. ์ด์ง ํธ๋ฆฌ๋ฅผ ํ์ฅํ์ฌ ๋ ๋ง์ ์์ ์์์ ๊ฐ์ง ์ ์๊ฒ ์ผ๋ฐํ์ํจ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ์ด๋ค. (์ด์ง ํธ๋ฆฌ๋ ์๋๋ค!)
-
์์ ์์ ๋ํ ์ผ๋ฐํ๋ฅผ ์งํํ๋ฉด์, ํ๋์ ๋ ๋ฒจ์ ๋ ์ ์ฅํ ์ ์๋ ๊ฒ๋ฟ ์๋๋ผ ํธ๋ฆฌ์ ๊ท ํ์ ์๋์ผ๋ก ๋ง์ถฐ์ฃผ๋ ๋ก์ง ๋ํ ๊ฐ์ถ์๋ค.
- ๋ฐ๋ผ์, ๊ท ํ ํธ๋ฆฌ์ ์ฅ์ ๊ณผ ํจ์จ์ ์ธ ๋ฐ์ดํฐ ๋ก๋์ ์ฅ์ ์ ๊ฐ์ถ์๋ค.
๋ ๋ฒจ์ ๋ ๋ง์ ์ ์ฅ์ด ๊ฐ๋ฅํ๋ค๋ ๊ฒ์ ์ฅ์
๋๋์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ ์, ๊ฒ์ ๊ตฌ์กฐ์ ๊ฒฝ์ฐ ํ๋์ ๋ ธ๋์ ๋ง์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง ์ ์๋ค๋ ๊ฒ์ ํฐ ์ฅ์ ์ด๋ค. ๋๋์ ๋ฐ์ดํฐ๋ ๋ฉ๋ชจ๋ฆฌ๋ณด๋ค ๋ธ๋ญ ๋จ์๋ก ์ ์ถ๋ ฅํ๋ HDD or SSD์ ์ ์ฅํด์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค.
- ex. ํ ๋ธ๋ญ์ด 1024๋ฐ์ดํธ๋ฉด, 2๋ฐ์ดํธ๋ฅผ ์ฝ์ผ๋ 1024๋ฐ์ดํธ๋ฅผ ์ฝ์ผ๋ ๋๊ฐ์ ์ ์ถ๋ ฅ ๋น์ฉ์ด ๋ฐ์ํ๋ค. ๋ฐ๋ผ์ ํ๋์ ๋ ธ๋๋ฅผ ๋ชจ๋ 1024๋ฐ์ดํธ๋ก ๊ฝ ์ฑ์์ ์กฐ์ ํ ์ ์๋ค๋ฉด ํจ์จ์ ์ผ ๊ฒ์ด๋ค.
B Tree๋ ์ด๋ฌํ ์ฅ์ ์ ํ ๋๋ก ๋ง์ DB ์์คํ ์ ์ธ๋ฑ์ค ์ ์ฅ ๋ฐฉ๋ฒ์ผ๋ก ์ ์ฉํ๊ณ ์๋ค.
๐ช ๊ท์น
- ๋ ธ๋์ ์๋ฃ์๊ฐ N๊ฐ์ด๋ฉด, ์์ ์๋ N + 1์ด์ด์ผ ํ๋ค.
- ๊ฐ ๋ ธ๋์ ์๋ฃ๋ ์ ๋ ฌ๋ ์ํ์ฌ์ผ ํ๋ค.
- ๋ฃจํธ ๋ ธ๋๋ ์ ์ด๋ 2๊ฐ ์ด์์ ์์์ ๊ฐ์ ธ์ผ ํ๋ค.
- ๋ฃจํธ ๋ ธ๋๋ฅผ ์ ์ธํ ๋ชจ๋ ๋ ธ๋๋ ์ ์ด๋ M/2๊ฐ์ ์๋ฃ๋ฅผ ๊ฐ์ง๊ณ ์์ด์ผ ํ๋ค.
- ์ธ๋ถ ๋ ธ๋๋ก ๊ฐ๋ ๊ฒฝ๋ก์ ๊ธธ์ด๋ ๋ชจ๋ ๊ฐ๋ค.
- ์ ๋ ฅ ์๋ฃ๋ ์ค๋ณต์ด ์์ด์ผ ํ๋ค.
๐งท B+ Tree
๋ฐ์ดํฐ์ ๋น ๋ฅธ ์ ๊ทผ์ ์ํ ์ธ๋ฑ์ค ์ญํ ๋ง ํ๋ ๋น๋จ๋ง ๋ ธ๋๊ฐ ์ถ๊ฐ๋ก ์๋ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ๊ธฐ์กด์ B Tree์ ๋ฐ์ดํฐ์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๊ตฌํ๋ ์์ธ ๊ตฌ์กฐ์ด๋ค.
- B Tree์ ๋ณํ ๊ตฌ์กฐ๋ก, index ๋ถ๋ถ๊ณผ leaf ๋ ธ๋๋ก ๊ตฌ์ฑ๋ ์์ฐจ ๋ฐ์ดํฐ ๋ถ๋ถ์ผ๋ก ์ด๋ฃจ์ด์ง๋ค. ์ธ๋ฑ์ค ๋ถ๋ถ์ key ๊ฐ์ leaf์ ์๋ key ๊ฐ์ ์ง์ ์ฐพ์๊ฐ๋๋ฐ ์ฌ์ฉํ๋ค.
p(fanout) ์ด๋ผ๋ ๊ฐ์ผ๋ก ํ node์ ๋ช ๊ฐ์ entry๊ฐ ์ฑ์์ ธ์ผ ํ๋์ง๋ฅผ ๋ํ๋ธ๋ค.
๐ช ์ฅ์
- ๋ธ๋ก ์ฌ์ด์ฆ๋ฅผ ๋ ๋ง์ด ์ฌ์ฉํ ์ ์๋ค. (key ๊ฐ์ ๋ํ HDD ์ ๊ทผ ์ฃผ์๊ฐ ์๊ธฐ ๋๋ฌธ์ด๋ค.)
- leaf ๋ ธ๋๋ผ๋ฆฌ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ์ฐ๊ฒฐ๋์ด ๋ฒ์ ํ์์ ๋งค์ฐ ์ ๋ฆฌํ๋ค.
๐ช ๋จ์
-
B Tree์ ๊ฒฝ์ฐ ์ต์ ์ผ์ด์ค์์๋ ๋ฃจํธ์์ ๋๋ ์ ์์ง๋ง, B+ Tree๋ ๋ฌด์กฐ๊ฑด leaf ๋ ธ๋๊น์ง ๋ด๋ ค๊ฐ๋ด์ผ ํ๋ค.
- ํ์ ๋น์ฉ์ด ํธ๋ฆฌ์ ๋์ด์ ๋น๋กํ๊ฒ ๋๋ค!
๐ช ์ฝ์
- ์ฝ์ ํ๋ ค๋ entry๊ฐ ์์นํ ๊ณณ์ ์ฐพ๋๋ค.
- ํด๋น node๊ฐ ์ถฉ๋ถํ ๊ณต๊ฐ์ด ์๋ค๋ฉด ์ฝ์ ํ๊ณ ์ข ๋ฃํ๋ค.
-
๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ, ํด๋น node๋ฅผ ๋ถ๋ฆฌํ๋ค.
- node์ ์ํธ๋ฆฌ๋ค์ ๋ถ๋ฐฐํ๊ณ ,
middle key๋ฅผ COPY UPํ๋ค.
- node์ ์ํธ๋ฆฌ๋ค์ ๋ถ๋ฐฐํ๊ณ ,
PUSH UPํ๋ฉด,
middle key์ ๋ํ Data pointer๊ฐ ์์ค๋๊ธฐ ๋๋ฌธ์ด๋ค.
๐ช ์ฝ์ ์ดํ ...
B+ Tree์ node๋ฅผ ์ฝ์ ํ ์ดํ ํธ๋ฆฌ์ ๋์ด๊ฐ ์ฆ๊ฐํ์ง ์์ ์๋ ์๊ณ , ์ฆ๊ฐํ ์๋ ์๋ค.
- B+ Tree์ ํ์ ๋น์ฉ์ ํธ๋ฆฌ์ ๋์ด์ ๋น๋กํ๋ค.
- ํธ๋ฆฌ๋ฅผ ์ฌ๋ถ๋ฐฐํจ์ผ๋ก์จ, ๋์ด๋ฅผ ๋ฎ์ถ ์ ์๋ค!
์ฌ๋ถ๋ฐฐ๋ฅผ ํตํด ํ์ ๋น์ฉ์ ๋ฎ์ถ ์๋ ์์ง๋ง, ํ๊ท I/O ๋ฐ์ฉ์ ์ฆ๊ฐ์ํจ๋ค.
๐ช ์ญ์
- ๋ฃจํธ๋ถํฐ, ํด๋น entry๊ฐ ์กด์ฌํ๋ leaf node๋ฅผ ์ฐพ๋๋ค.
- ํด๋น node์์ entry๋ฅผ ์ง์๋ ์ฑ์์ ธ์ผ ํ๋
p๋ฅผ ๋ง์กฑํ๋ค๋ฉด ๊ทธ๋๋ก ์ญ์ ํ๋ค. -
์ง์ด ํ node์ entry ์๊ฐ
p - 1์ด๋ผ๋ฉด, ์ฃผ๋ณ leaf node(๊ฐ์ ๋ถ๋ชจ๋ฅผ ๊ฐ์ง๋ ์ฃผ๋ณ node)๋ก๋ถํฐ entry๋ฅผ ๋น๋ ค์p๋ฅผ ๋ง์กฑ์ํจ๋ค.- ์ด๋
middle key์ ๋ณ๊ฒฝ์ ์ ๋ฐํ๋ค. - ๋ง์ฝ ์ฃผ๋ณ leaf node๋ก๋ถํฐ ๋น๋ ค์ฌ ์ ์๋ค๋ฉด, ๊ทธ leaf node์ ๊ฒฐํฉํ๋ค.
- ๊ฒฐํฉ์ด ๋ฐ์ํ๋ฉด, ๋ ์ค ํ node๋ ์ ๊ฑฐํ๋ค.
- ๊ฒฐํฉ์ ํตํด ํธ๋ฆฌ์ ๋์ด๊ฐ ๊ฐ์ํ ์๋ ์๋ค.
- ์ด๋
๐งท B Tree์ B+ Tree ๋น๊ต
- B Tree๋ ๊ฐ ๋ ธ๋์ ๋ฐ์ดํฐ๊ฐ ์ ์ฅ๋๋ค.
- B+ Tree๋ index ๋ ธ๋์ leaf ๋ ธ๋๋ก ๋ถ๋ฆฌ๋์ด ์ ์ฅ๋๋ค. (๋ํ leaf ๋ ธ๋๋ ์๋ก ์ฐ๊ฒฐ๋์ด ์์ด ์์ ์ ๊ทผ์ด๋ ์์ฐจ ์ ๊ทผ ๋ชจ๋ ์ฑ๋ฅ์ด ์ข๋ค.)
- B Tree๋ ๊ฐ ๋ ธ๋์์ key์ data ๋ชจ๋ ๋ค์ด๊ฐ ์ ์๊ณ , data๋ disk block์ผ๋ก ํฌ์ธํฐ๊ฐ ๋ ์ ์๋ค.
-
B+ Tree๋ ๊ฐ ๋ ธ๋์์ key๋ง ๋ค์ด๊ฐ ์ ์๋ค. ๋ฐ๋ผ์ data๋ ๋ชจ๋ leaf ๋ ธ๋์๋ง ์กด์ฌํ๋ค.
- B+ Tree์ ์ฝ์ ๊ณผ ์ญ์ ๋ ๋ชจ๋ leaf ๋ ธ๋์์๋ง ๋ฐ์ํ๋ค.